Problem statement: zenit17kkk

Komplikovaná výrobná linka

Počet bodov: 40, časový limit: 1500ms

Nudná firma sa rozhodla, že si v našich končinách postaví továreň. Všetko išlo dobre, továreň bola postavená bez väčších problémov. Problémy sa však čoskoro dostavili – pri stavbe nastala chyba a komponenty dorazia pred univerzálny skladací prístroj v nesprávnom poradí.

Továreň je už postavená a veľké zásahy sa do nej spraviť nedajú. Našťastie je pred univerzálnym skladacím prístrojom ešte troška miesta na umiestnenie jednej špeciálnej mašiny. Touto mašinou je polouniverzálny rotátor.

Univerzálny rotátor je mašina, ktorá si zvolí ľubovoľné číslo \(k\) a súvislý úsek komponentov. Vybraný úsek následne cyklicky posunie o \(k\) miest doprava. Pre úsek dĺžky \(m\) to znamená, že komponent na pozícii \(i\) sa posunie na pozíciu \([(i + k) \mod m]\)¹, kde \([a \mod b]\) označuje zvyšok po delení \(a\) číslom \(b\).

Polouniverzálny rotátor dokáže takmer to isté, čo univerzálny rotátor. Rozdiel je v tom, že si môže vybrať iba taký úsek komponentov, ktorý je symetrický podľa stredu. Ak máme \(n\) komponentov dohromady, začiatok rotovaného úseku, označme ho \(x\), musí byť niekde v prvej polovici komponentov: \(x < \frac{n}{2}\). Koniec, a teda posledný rotovaný komponent, musí byť presne na pozícii \(n - x - 1\)².

Úloha

Na vstupe dostanete čísla \(1\) až \(n\) v nejakom poradí. Vašim cieľom je vytvoriť postupnosť príkazov pre polouniverzálny rotátor, ktorá tieto čísla usporiada od najmenšieho po najväčšie. Nemôžete použiť viac, ako \(3\,000\) príkazov.

Vstup a výstup

Na prvom riadku vstupu dostanete číslo \(n\). Na druhom riadku dostanete \(n\) čísel z rozsahu \(1\) až \(n\), pričom každé číslo sa objaví práve raz.

Na prvý riadok vypíšte číslo \(m\) – počet inštrukcií, ktoré chcete vykonať. Ďalej vypíšte \(m\) riadkov – postupnosť inštrukcií. Každá inštrukcia pozostáva z dvoch čísel \(d_i\) a \(k_i\) – dĺžka rotovanej postupnosti³ a počet pozícií, o ktoré sa má otočiť. Pokiaľ je \(n\) párne, musí byť každé \(d_i\) párne. Pokiaľ je \(n\) nepárne, musí byť každé \(d_i\) nepárne.

Počet inštrukcií nesmie prekročiť \(3\,000\). Pokiaľ neexistuje postupnosť inštrukcií, ktorá komponenty usporiada, vypíšte jediný riadok obsahujúci \(-1\). Pokiaľ existuje viac správnych postupností inštrukcií, vypíšte ktorúkoľvek. Ak existuje nejaká postupnosť inštrukcií, ktorá pole usporiada, zaručene existuje aj postupnosť nanajvýš \(3\,000\) inštrukcií, ktorá ho usporiada.

Príklad

Input:

4
2 1 4 3

Output:

3
2 1
4 2
2 1

Input:

3
3 2 1

Output:

-1

Input:

3
1 2 3

Output:

0